package com.algorithm;

import java.util.Arrays;

public class A001螺旋数组 {


    public static void main(String[] args) {

        int[][] ints = method002(3);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 方法一：模拟
     * 模拟矩阵的生成。按照要求，初始位置设为矩阵的左上角，初始方向设为向右。若下一步的位置超出矩阵边界，或者是之前访问过的位置，则顺时针旋转，进入下一个方向。
     * 如此反复直至填入 n*n个元素。
     * 记 matrix 为生成的矩阵，其初始元素设为 0。由于填入的元素均为正数，我们可以判断当前位置的元素值，若不为 0，则说明已经访问过此位置。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/spiral-matrix-ii/solution/luo-xuan-ju-zhen-ii-by-leetcode-solution-f7fp/
     */
    public static int[][] method01(int n) {
        //最大值
        int max = n * n;
        int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//表示转向
        int curNum = 1;
        //matrix表示目标数组
        int[][] matrix = new int[n][n];
        int row = 0;
        int column = 0;
        int directIndex = 0;
        while (curNum <= max) {
            matrix[row][column] = curNum++;
            int nextRow = row + direction[directIndex][0];
            int nextColumn = column + direction[directIndex][1];
            //是否需要转向
            if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n
                    || matrix[nextRow][nextColumn] != 0) {
                directIndex = (directIndex + 1) % 4;
            }
            //移动位置
            row = row + direction[directIndex][0];
            column = column + direction[directIndex][1];
        }
        return matrix;
    }

    /**
     * 方法二：按层模拟
     * 可以将矩阵看成若干层，首先填入矩阵最外层的元素，其次填入矩阵次外层的元素，直到填入矩阵最内层的元素。
     */
    public static int[][] method002(int n) {
        //目标数组
        int[][] arr = new int[n][n];
        //计数
        int curr = 1;
        //上边
        int top = 0;
        //下边
        int bottom = n - 1;
        //左边
        int left = 0;
        //右边
        int right = n - 1;
        while (curr <= n * n && left <= right && top <= bottom) {
            //上
            for (int i = left; i <= right && arr[top][i] == 0; i++) {
                arr[top][i] = curr++;
            }
            //右
            for (int i = top + 1; i <= bottom && arr[i][right] == 0; i++) {
                arr[i][right] = curr++;
            }
            //下
            for (int i = right-1; i >= left && arr[bottom][i] == 0; i--) {
                arr[bottom][i] = curr++;
            }
            //左
            for (int i = bottom-1; i >= top && arr[i][left] == 0; i--) {
                arr[i][left] = curr++;
            }
            //内一层
            top++;
            bottom--;
            left++;
            right--;
        }
        return arr;
    }
}
